﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,
nCr = 	
n!
r!(n−r)!
	,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of  nCr, for 1 ≤ n ≤ 100, are greater than one-million?

     * */
    class Problem53 : IProblem
    {
        public string Calculate()
        {
            //taktika, zbrajaj
            //n povrh r za sve n od 1 do 100 i r od 1 do n

            long sum = 0;

            for (int n = 1; n <= 100; n++)
            {
                for (int r = 1; r <= n; r++)
                {
                    if(BinomeExceedsLimit(n, r, 1000000))
                        sum++;
                }
            }

            return sum.ToString();
        }

        bool BinomeExceedsLimit(int n, int k, int limit)
        {
            int tempK = k;
            double total = 1;
            for (int i = n; i > n - k; i--)
            {
                total *= i;
                while (total > tempK && tempK > 1)
                {
                    total /= tempK;
                    tempK--;
                }
            }

            while (total > tempK && tempK > 1)
            {
                if (total < limit)
                    return false;
                total /= tempK;
                tempK--;
            }

            if (total < limit)
                return false;
            return true;
        }
    }
}
